package algorithm.dynamicProgramming.p70;

import java.util.Arrays;

class Solution_v1 {
    private int[] memo;

    public int climbStairs(int n) {
        memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return fib(n);
    }

    private int fib(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        if(memo[n] == -1)
            memo[n] = fib(n - 2) + fib(n - 1);
        return memo[n];
    }

    public static void main(String[] args) {
        System.out.println(new Solution_v1().climbStairs(0));
    }
}